package leetcode;
/**
 * 279.完全平方数
 * 给定正整数 n，找到若⼲个完全平⽅数（⽐如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平⽅数的个数最少。
 * 给你⼀个整数 n ，返回和为 n 的完全平⽅数的 最少数量 。
 * 完全平⽅数是⼀个整数，其值等于另⼀个整数的平⽅；换句话说，其值等于⼀个整数⾃乘的积。例如，
 * 1、4、9 和 16 都是完全平⽅数，⽽ 3 和 11 不是。
 * 示例 1：
 * 输⼊：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 示例 2：
 * 输⼊：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 */
import java.util.*;
public class Num_279 {
    //同样是完全背包问题，而且和322.零钱兑换思路一致，只是需要自己定义coins[]的内容
    public int numSquares(int n) {

        //自定义coins[]的内容
        List<Integer> list = new ArrayList<>();
        //边界条件就是list中的任意数 <= n
        for(int i=1; i*i<=n; i++){
            list.add(i*i);
        }

        //dp[i][j]表示前i个完全平方数凑出j的最少数量
        int[][] dp = new int[list.size()+1][n+1];
        //初始化
        //前i个硬币凑出0的数量就是0，dp[i][0] = 0
        //第1个完全平方数是1，所以初始化 i=1的情况，这道题也因此不存在凑不出n的情况
        for(int j=0; j<=n; j++){
            dp[1][j] = j;
        }
        //开始二重循环遍历
        for(int i = 2; i <= list.size(); i++){
            for(int j = 1; j <= n; j++){
                //不选第i个的情况
                dp[i][j] = dp[i-1][j];
                //选择第i个的情况
                if(j >= list.get(i-1)){
                    // dp[i][j] = dp[i][j-list.get(i-1)] + 1; 这是选了第i个的情况，需要比较两种情况哪种消耗数量更少
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-list.get(i-1)] + 1);
                }
            }
        }
        return dp[list.size()][n];
    }

    /** 复习 **/
    public int numSquares2(int n) {
        //也是完全背包的转型，和上一题相似，不过这道题元素需要自己创
        //可以根据n的值，适当创建元素个数
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i * i <= n; i++){
            list.add(i * i);
        }
        //dp[i][j]表示前i个元素凑出j的最少数量
        int[][] dp = new int[list.size() + 1][n + 1];
        //初始化
        //前i个元素凑出0的最少数量就是0，dp[i][0] = 0
        //前0个元素凑出j的最少数量为-1
        for(int j = 1; j <= n; j++){
            dp[0][j] = -1;
        }
        //先遍历元素
        for(int i = 1; i <= list.size(); i++){
            //再遍历容量
            for(int j = 1; j <= n; j++){
                //不选第i个元素
                dp[i][j] = dp[i - 1][j];
                //选第i个元素: dp[i][j - list.get(i-1)] + 1
                if(list.get(i-1) <= j && dp[i][j - list.get(i-1)] != -1){
                    if(dp[i - 1][j] == -1){
                        dp[i][j] = dp[i][j - list.get(i-1)] + 1;
                    }else{
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - list.get(i-1)] + 1);
                    }
                }
            }
        }
        return dp[list.size()][n];
    }
}
